Data streaming systems are used to perform real-time analysis and recording of flows of data records. Many data streaming systems are best-effort systems, which may drop records whenever they are under overload conditions. Similarly, there may be instances where data streaming systems may experience an unexpected failure of a data source where it may be difficult to ascertain as to what records have already been processed from the failed data source given the sudden interruption. As such, it is possible that the data streaming systems may simply end up processing the same records multiple times, i.e., “over accounting” of the records. Although dropping some records or over accounting the same records multiple times may be acceptable for some applications, other applications will require a guarantee that each and every record is accounted for and processed only once. Furthermore, in many data stream processing system, every record in the steam contains a timestamp. While the data stream processing system expects record timestamps to increase over the long term, it is difficult to ensure that records in the stream will arrive in monotonically increasing timestamp order.